package com.example.algorithm.sorts;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.function.IntFunction;
import java.util.stream.Collectors;

/**
 * 给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
 *  注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
 *
 *  示例 1：
 * 输入：nums = [10,2]
 * 输出："210"
 *
 *  示例 2：
 * 输入：nums = [3,30,34,5,9]
 * 输出："9534330"
 *
 *  示例 3：
 * 输入：nums = [1]
 * 输出："1"
 *
 *  示例 4：
 * 输入：nums = [10]
 * 输出："10"
 */
public class Leetcode179_LargestNumber {
    public static void main(String[] args) {
        int[] nums = {3, 30, 34, 5, 9};

        System.out.println(new Solution().largestNumber(nums));
    }

    static class Solution {

        /**
         * 解法二:堆
         * @param nums
         * @return
         */
        private String largestNumber2(int[] nums) {
            // 3, 30, 34, 5, 9
            // 330 303
            Queue<String> heap = new PriorityQueue<>((s1, s2) -> (s2 + s1).compareTo(s1 + s2));
            for (int num : nums) {
                heap.offer(String.valueOf(num));
            }

            StringBuilder sb = new StringBuilder();
            while (!heap.isEmpty()) {
                sb.append(heap.poll());
            }
            if(sb.charAt(0) == '0') return "0";
            return sb.toString();
        }

        /**
         * 解法一:自定义排序
         * 比较输入数组的每个元素的最高位，最高位相同的时候比较次高位，以此类推
         *
         * 完成排序，然后把它们拼接起来即可
         * @param nums
         * @return
         */
        private String largestNumber1(int[] nums) {
            int n = nums.length;
            // 转换成包装类型，以便传入 Comparator 对象
            Integer[] numsArr = new Integer[n];
            for (int i = 0; i < n; i++) {
                numsArr[i] = nums[i];
            }

            Integer[] arr = Arrays.stream(nums).boxed().toArray(Integer[] :: new);
//            System.out.println(Arrays.toString(arr));

            // 91 92
            Arrays.sort(numsArr, (x, y) -> {
                long sx = 10, sy = 10;
                while (sx <= x) {
                    sx *= 10;
                }
                while (sy <= y) {
                    sy *= 10;
                }
                return (int) (-sy * x - y + sx * y + x);
            });

            System.out.println(Arrays.toString(numsArr));
            StringBuilder sb = new StringBuilder();
            for (Integer num : numsArr) {
                sb.append(num);
            }

            if (sb.charAt(0) == '0') return "0";
            return sb.toString();
        }

        public String largestNumber(int[] nums) {
            return largestNumber2(nums);
        }
    }
}
